package leetcode.hash和set;

import java.util.*;

/**
 * 存在重复元素 II
 *
 * 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，
 * 使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。
 *
 * 示例 1:
 *
 * 输入: nums = [1,2,3,1], k = 3
 * 输出: true
 *
 * 注意：题意里面这个K指的是 <= K，而非绝对 = K
 */
public class Test219存在重复元素II {

    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        // 维护一个长度为k的滑动窗口
        // 在窗口内找到了，就返回 true

//        List<Integer> list = new ArrayList<>();   超时！
//        for (int i = 0; i < nums.length; i++) {
//            if (list.contains(nums[i])) {
//                return true;
//            }
//            list.add(nums[i]);
//            if (list.size() == k+1) {
//                list.remove(0);
//            }
//        }
//        return false;

        // map 作为查找表，存储 nums[i] 以及对应的 index
        Map<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        // 遍历数组，若当前的 num[i] 存在于 map 里面，
        // 就计算他的 index 与当前处理的 i 的绝对值是否不超过 k
        // 由于是 map 结构，后面遇到相同的 nums[i] 的时候会更新 index 的值，所以不必担心重复数据的问题
        for (int i = 0; i < len; i++) {
            if (map.containsKey(nums[i]) && Math.abs(map.get(nums[i]) - i) <= k) {
                return true;
            }
            // map 里面没有 nums[i] 就添加进去
            // 或者遇到重复数据，更新 index
            map.put(nums[i], i);
        }

        return false;
    }

    public static void main(String[] args) {
//        int[] nums = new int[]{1,2,3,1};
//        int k = 3;

//        int[] nums = new int[]{1,0,1,1};
//        int k = 1;


        int[] nums = new int[]{1,2,3,1,2,3};
        int k = 2;
        System.out.println(containsNearbyDuplicate(nums, k));
    }
}
